class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1
        if n < 0:
            return 1 / self.myPow(x, -n)
        if n % 2 == 0:
            half = self.myPow(x, n // 2)
            return half * half
        else:
            return x * self.myPow(x, n - 1)
if __name__ == '__main__':
    s = Solution()
    print(s.myPow(2, 6))

# 思路：
# 如果n为0，则返回1
# 如果n为负数，则返回1/x^(-n)
# 如果n为偶数，则返回x^(n/2) * x^(n/2)
# 如果n为奇数，则返回x * x^(n-1)
# 不管n是偶数还是奇数，用递归之后，最后都会使得n=0